home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / BFSORTS.ARJ / HSORT.C next >
C/C++ Source or Header  |  1991-03-31  |  6KB  |  224 lines
  1. /***********************************************************************/
  2. /*  SORT(): Non-Recursive Heap Sort function.                          */
  3. /*  See the function declaration for calling information.              */
  4. /* Function is by Bruce Feist; please contact me on CompuServe with    */
  5. /*    a message on BPROGB, MACDEV, or EASYPLEX if you have any         */
  6. /*    questions or problems.                                           */
  7. /* You can also reach me at the Enlightened Board, at (703) 370-9528,  */
  8. /*   N/8/1                                                             */
  9. /* Feel free to make use of this code in your own programs.            */
  10. /***********************************************************************/
  11.  
  12. #define VERBOSE (0)
  13.  
  14. #include <process.h>
  15. #include <alloc.h>
  16. #include <stdlib.h>
  17. #include <mem.h>
  18. #include <stddef.h>
  19. #include <stdio.h>
  20.  
  21. #include "sort.h"
  22.  
  23. static void build_heap (void), extract_heap (void);
  24. static void heapify (int, int);
  25.  
  26. static void show_node (int);
  27. #if VERBOSE
  28. static void show_heap (void);
  29. #endif
  30.  
  31. /* heapsort uses an array of pointers as its data structure to   */
  32. /* represent the heap.                                           */
  33. /* Children of slot i are slots 2i+1 and 2i+2.                   */
  34.  
  35. /* Note:  as an alternative, we could have made the input array */
  36. /* into a heap (instead of messing with the pointers.           */
  37.  
  38. static char *base, *temp_record;
  39. static int nelem, width, (*compare)(void *, void *);
  40.  
  41. int
  42. hsort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
  43.  
  44. {
  45.   base = pbase;
  46.   nelem = pnelem;
  47.   width = pwidth;
  48.   compare = pcompare;
  49.   if ((temp_record = malloc (pwidth)) == NULL)
  50.     return S_NOMEM;
  51.  
  52. #if VERBOSE
  53.   printf ("Sort (base = %p, n = %u, w = %u)\n", base, nelem, width);
  54. #endif
  55.  
  56.   build_heap ();
  57.   extract_heap ();
  58.  
  59.   free (temp_record);
  60.  
  61.   return S_OK;
  62.   } /* end hsort */
  63.  
  64.  
  65. void
  66. build_heap()
  67.  
  68. {
  69.   register int left;
  70.   register char *left_ptr;
  71.   int right;
  72.  
  73. #if VERBOSE
  74.   puts ("Building heap. . .\n");
  75. #endif
  76.  
  77.   right = nelem - 1;
  78.   for (left = (nelem >> 1) - 1, left_ptr = base + width * left;
  79.        1; /* keep going until the 'break' */
  80.        left--, left_ptr -= width)
  81.   {
  82. #if VERBOSE
  83.     printf ("temp <- %d to start heapification.\n", left);
  84. #endif
  85.     memcpy (temp_record, left_ptr, width);
  86.     heapify (left, right);
  87.     if (! left)
  88.       break;
  89.     }
  90.  
  91.   } /* end build_heap */
  92.  
  93.  
  94. void
  95. extract_heap ()
  96. {
  97.   register int right;
  98.   register char *right_ptr;
  99.  
  100. #if VERBOSE
  101.   puts ("Extracting from heap. . .\n");
  102. #endif
  103.  
  104.   for (right = nelem - 1, right_ptr = base + width * right;
  105.        1; /* continue until the 'break' */
  106.        right_ptr -= width)
  107.   {
  108.     memcpy (temp_record, right_ptr, width);
  109.     memcpy (right_ptr,   base,      width);
  110. #if VERBOSE
  111.     printf ("temp <- %d to start extract\n", right);
  112.     printf ("%d <- %d to start extract\n", right, 0);
  113.     printf ("Returning %lf\n", ((double *) base) [right]);
  114. #endif
  115.     if (! --right)
  116.       break;
  117.     heapify (0, right);
  118.     }
  119. #if VERBOSE
  120.   printf ("%d <- temp to finish extract\n", 0);
  121. #endif
  122.   memcpy (base, temp_record, width);
  123.   } /* end extract_heap */
  124.  
  125.  
  126. /* When heapify is called, (left+1,right) is already heapified and       */
  127. /* temp_record contains what we'd like to add to it to make (left,right) */
  128. /* a heap.                                                               */
  129. /*   So, we look for the first descendent of 'left' that's bigger than   */
  130. /* it.  All of its ancestors move up a generation, and temp_record       */
  131. /* becomes its parent.                                                   */
  132.  
  133. void
  134. heapify (int left, int right)
  135.  
  136. {
  137.   register int  child;
  138.   register char *ptr_child;
  139.   char          *ptr_child2, *ptr_parent;
  140.  
  141.   child = left;
  142.   ptr_child = base + child * width;
  143.  
  144. #if VERBOSE
  145.   show_heap();
  146.   printf ("Heapifying from %d to %d.\n", left, right);
  147. #endif
  148.  
  149.   while (1) /* continue until the 'break' */
  150.   {
  151.     child <<= 1;
  152.     child++;
  153.     ptr_parent = ptr_child;
  154.  
  155.     if (child > right)  /* if parent was a leaf, replace with temp_record */
  156.     {
  157. #if VERBOSE
  158.       printf ("%d <- temp since %d is leaf.\n", parent, parent);
  159. #endif
  160.       memcpy (ptr_parent, temp_record, width);
  161.       break;
  162.       } /* end if */
  163.  
  164.     ptr_child = base + child * width;
  165.     if (child < right)  /* Is there more than one child? */
  166.     {
  167.       /* Use the biggest child. */
  168.       if (compare (ptr_child, ptr_child2 = ptr_child + width) < 0)
  169.       {
  170.         child++;
  171.         ptr_child = ptr_child2;
  172.         }  /* end if ptr_child < ptr_child2 */
  173.       } /* end if child < right */
  174.  
  175.     if (compare (temp_record, ptr_child) >= 0)  /* Is temp_record bigger? */
  176.     {
  177. #if VERBOSE
  178.       printf ("%d <- temp since temp is bigger than %d.\n", parent, child1);
  179. #endif
  180.       memcpy (ptr_parent, temp_record, width);
  181.       break;
  182.       }
  183.  
  184. #if VERBOSE
  185.     printf ("%d <- %d since we're not done yet\n", parent, child1);
  186. #endif
  187.     memcpy (ptr_parent, ptr_child, width);      /* Promote by a generation */
  188.     }  /* end while TRUE */
  189.  
  190. #if VERBOSE
  191.   puts ("Done heapifying.");
  192.   show_heap();
  193. #endif
  194.   } /* end heapify */
  195.  
  196.  
  197. void
  198. show_heap ()
  199. {
  200.   puts ("The heap:");
  201.   show_node (0);
  202.   }
  203.  
  204. void
  205. show_node (int node_id)
  206. {
  207.   int child1, child2, ancestor;
  208.  
  209.   child1 = node_id * 2 + 1;
  210.   child2 = child1 + 1;
  211.  
  212.   printf ("%.4lf\t", ((double *) base) [node_id]);
  213.   if (child1 < nelem)
  214.     show_node (child1);
  215.   else
  216.      putchar ('\n');
  217.  
  218.   if (child2 < nelem)
  219.   {
  220.     for (ancestor = 1; ancestor < child2; ancestor <<= 1)
  221.       putchar ('\t');
  222.     show_node (child2);
  223.     }
  224.   } /* end show_node */